package 递归.归并;

import java.util.Arrays;

/*归并排序*/
/*循环不变量*/
public class MergeSortNew {
    private MergeSortNew(){};
    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr, 0, arr.length);
    }
    /*[l, r)*/
    public static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        /*if r - l小于一定的数，用插入排序*/
        /*r - 1 <= l*/
        if (l >= r - 1){
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid, r);
        /*优化成为o(n)*/
        if (arr[mid - 1].compareTo(arr[mid]) > 0)
            merge(arr, l , mid, r);
    }
    /*自底向上归并排序*/
    public static <E extends Comparable<E>> void sortBU(E[] arr){
        /*遍历合并的区间长度*/
        for(int sz = 1; sz < arr.length; sz *= 2){
            /*遍历合并的两个区间1的起始位置*/
            for (int i = 0; i+sz<arr.length; i+= (2*sz)){
                merge(arr, i, i+sz-1,
                        Math.min(i+sz+sz-1, arr.length - 1));
            }
        }
    }
    /*[l, mid), [mid, r)*/
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r){
        /*copy从0开始*/
        /*优化辅助空间拿到sort里面*/
        E[] copy = Arrays.copyOfRange(arr, l, r);
        int i = l;
        int j = mid;
        for (int k = l; k < r; k++) {
            if (i >= mid){
                arr[k] = copy[j-l];
                j++;
            }else if(j >= r){
                arr[k] = copy[i-l];
                i++;
            }else if(copy[i-l].compareTo(copy[j-l])<=0){
                arr[k] = copy[i-l];
                i++;
            }else {
                arr[k] = copy[j - l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        Integer [] a = {8,4,3,5,7,6};
        MergeSortNew.sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}
